1
Principes de la minimisation sans contrainte
MATH008Lesson 9
00:00
Nous passons de l'existence théorique d'un minimum à l'engine algorithmique de l'optimisation. Notre objectif principal est de minimiser $f(x)$ (9.1) où $f: \mathbf{R}^n \to \mathbf{R}$ est convexe et deux fois continûment différentiable. Puisque $f$ est différentiable et convexe, une condition nécessaire et suffisante pour qu'un point $x^*$ soit optimal est $\nabla f(x^*) = 0$.

Le cadre algorithmique

Les solutions numériques construisent une suite de minimisation: une suite de points $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ telle que $f(x^{(k)}) \to p^*$ lorsque $k \to \infty$. Chaque étape met à jour la position par $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, où $\Delta x$ est une direction de descente.

Initialisation et convergence

Les méthodes décrites dans ce chapitre nécessitent un point de départ approprié $x^{(0)}$. Le point de départ doit appartenir à $\text{dom } f$, et en outre l'ensemble de niveau inférieur $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ doit être fermé. Cela garantit que la suite reste dans une région bien comportée où le hessien fournit des informations utiles.

Directions de descente

La direction la plus simple est $\Delta x = -\nabla f(x)$. Toutefois, l'efficacité exige souvent de tenir compte de différentes géométries à travers la direction de descente la plus raide:

  • Norme quadratique : $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
  • Norme $L_\infty$ : $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Descente par coordonnées).

Modèles d'ordre deux et régions de confiance

La méthode de Newton utilise une approximation de Taylor d'ordre deux : $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Ce polynôme quadratique est minimisé lorsque $v = \Delta x_{nt}$ (pas de Newton). Nous définissons une région de confiance : l'ensemble $\{v \mid \|v\|_2 \le \gamma\}$. Le paramètre $\gamma$ reflète notre confiance dans le modèle d'ordre deux. Lorsque le modèle est précis, nous résolvons la direction via $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ dans les systèmes KKT.

🎯 Principes fondamentaux de convergence
L'efficacité est mesurée par la vitesse à laquelle l'erreur $f(x^{(k)}) - p^*$ disparaît. Pour les fonctions fortement convexes, l'erreur $f(x^{(k)}) - p^*$ converge vers zéro au moins aussi vite qu'une série géométrique. Dans le contexte des méthodes numériques itératives, cela s'appelle la convergence linéaire.
  • Borne de sous-optimalité : $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, valide si $\lambda(x) < 1$.
  • Somme de self-concordance : Si $f_1, f_2$ sont auto-concordantes, alors $f_1 + f_2$ est auto-concordante.
  • Éparpillement du hessien : L'efficacité est améliorée si la condition de structure en bande du hessien : $\nabla^2 f(x)_{ij} = 0$ pour $|i-j| > k$ est satisfaite.